package com.fang.sort;

import java.lang.reflect.Array;
import java.util.Comparator;

/**
 * <p>
 * 算法描述
 * </p>
 * 
 * <p>
 * 1、将n个元素分成两个含n/2元素的子序列
 * </p>
 * <p>
 * 2、用归并排序将两个子序列递归排序（最后可以将整个原序列分解成n个子序列）
 * </p>
 * <p>
 * 3、 合并两个已排序好的序列
 * </p>
 *
 * 
 */
public class MergeSort {
	public static void main(String[] args) {
		Integer[] sort = { 2, 5, 45, 87, 1, 254, 58 };

		MergeSort mergeSort = new MergeSort();
		Integer[] data = mergeSort.sort(sort, 0, sort.length - 1, new Comparator<Integer>() {
			@Override
			public int compare(Integer data1, Integer data2) {
				if (data1 < data2)
					return 1;
				if (data1 > data2)
					return -1;
				return 0;
			}
		});
		for (Integer integer : data) {
			System.out.print(integer + "   ");
		}
	}

	public <T> T[] sort(T[] data, int left, int right, Comparator<? super T> comparator) {
		if (data == null) {
			return data;
		}

		if (left < right) {
			int mid = (left + right) >> 1;
			// 对数组左半部分进行归并排序
			sort(data, left, mid, comparator);
			// 对数组的右半部分进行归并排序
			sort(data, mid + 1, right, comparator);
			// 合并左右两个子序列
			merge(data, left, mid, right, comparator);
		}

		return data;
	}

	private <T> T[] merge(T[] data, int left, int mid, int right, Comparator<? super T> comparator) {
		int i = left; // 第一段序列的下标
		int j = mid + 1;// 第二段序列的下标
		@SuppressWarnings("unchecked")
		T[] tempData = (T[]) Array.newInstance(data.getClass().getComponentType(), right - left + 1);
		int count = 0;
		while ((i <= mid) && (j <= right)) {
			if (comparator.compare(data[i], data[j]) > 0) {
				tempData[count++] = data[i++];
			} else {
				tempData[count++] = data[j++];
			}
		}
		// 若第一段序列还没扫描完，将其全部复制到合并序列
		while (i <= mid) {
			tempData[count++] = data[i++];
		}
		// 若第二段序列还没扫描完，将其全部复制到合并序列
		while (j <= right) {
			tempData[count++] = data[j++];
		}

		for (int k = 0; k < tempData.length; k++) {
			data[left + k] = tempData[k];
		}
		return data;
	}
}
